// https://www.lintcode.com/problem/digit-counts/

public class Solution {
    /**
     * @param k: An integer
     * @param n: An integer
     * @return: An integer denote the count of digit k in 1..n
     */
    public int digitCounts(int k, int n) {
        // write your code here
        int ret = 0;
        for (int i = 0; i <= n; ++i) {
            ret += checkK(i, k);
        }
        return ret;
    }
    
    protected int checkK(int i, int k) {
        if (i == k) {
            return 1;
        }
        int ret = 0;
        while (i > 0) {
            if ((i % 10) == k) {
                ++ret;
            }
            i /= 10;
        }
        return ret;
    }
}